package com.xie.leetcode.array;

//301. 删除无效的括号
//        给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
//
//        返回所有可能的结果。答案可以按 任意顺序 返回。
//
//
//
//        示例 1：
//
//        输入：s = "()())()"
//        输出：["(())()","()()()"]
//        示例 2：
//
//        输入：s = "(a)())()"
//        输出：["(a())()","(a)()()"]
//        示例 3：
//
//        输入：s = ")("
//        输出：[""]
//
//
//        提示：
//
//        1 <= s.length <= 25
//        s 由小写英文字母以及括号 '(' 和 ')' 组成
//        s 中至多含 20 个括号

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author xiezhendong
 * @date 2021/10/27
 */
public class RemoveInvalidParentheses {

    public static void main(String[] args) {
        RemoveInvalidParentheses removeInvalidParentheses = new RemoveInvalidParentheses();
        System.out.println(removeInvalidParentheses.removeInvalidParentheses("()())()"));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses("()()(()"));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses("(())()"));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses("(a)())()"));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses(")("));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses("((a("));
        System.out.println(removeInvalidParentheses.removeInvalidParentheses(")b))"));
    }

    public List<String> removeInvalidParentheses(String s) {
        List<String> list = new ArrayList<>();
        if (s == null || "".equals(s)) {
            list.add(s);
            return list;
        }

        Set<String> sSet = new HashSet<>();
        sSet.add(s);
        while (true) {
            list = new ArrayList<>();
            for (String x : sSet) {
                if (check(x)) {
                    list.add(x);
                }
            }
            if (!list.isEmpty()) {
                return list;
            }

            Set<String> nextSet = new HashSet<>();
            for (String x : sSet) {
                for (int i = 0; i < x.length(); i++) {
                    if (x.charAt(i) == '(' || x.charAt(i) == ')') {
                        nextSet.add(x.substring(0, i) + x.substring(i + 1, x.length()));
                    }
                }
            }
            sSet = nextSet;
        }
    }

    private boolean check(String s) {
        char[] sChars = s.toCharArray();
        int num = 0;
        for (char sChar : sChars) {
            String s1 = String.valueOf(sChar);
            if (")".equals(s1)) {
                num = num - 1;
            }
            if ("(".equals(s1)) {
                num = num + 1;
            }
            if (num < 0) {
                return false;
            }
        }
        return num == 0;
    }
}
